package com.demo.jzoffer2;

import org.junit.Test;

/**
 * @author gy
 * @date 2023/03
 */
public class Test0325_01 {

    /**
     * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
     * 丑数的递推性质：丑数 = 某较小的丑数 * 某因子 得到
     * @param n
     * @return
     */
    public int nthUglyNumber(int n) {
        // 不同丑数因子的丑数指针，初始化都指向第一个丑数
        int a = 0, b = 0,c = 0;
        // 记录丑数的数列，丑数的性质：丑数 = 某较小丑数 * 某因子
        int[] dp = new int[n];
        // 初始化第一个丑数
        dp[0] = 1;
        // 遍历n个丑数
        for (int i = 1; i < n; i++) {
            // 2,3,5分别为三个丑数因子
            // 丑数因子的指针所指向的丑数 * 丑数因子 = 新的丑数‘
            int n2 = dp[a] * 2,n3 = dp[b] * 3, n5 = dp[c] * 5;
            // 为了保证丑数的升序序列，故需要取三个新丑数中最小的一个
            dp[i] = Math.min(Math.min(n2,n3),n5);
            // 被记录的丑数所使用的因子的丑数指针右移动，方便该因子与其右一个丑数相乘得到最大的丑数
            if (dp[i] == n2){
                a++;
            }
            if (dp[i] == n3){
                b++;
            }
            if (dp[i] == n5) {
                c++;
            }
        }
        // 返回第 n 个丑数
        return dp[n-1];
    }

    @Test
    public void m1() {

    }

    @Test
    public void m2() {

    }

    @Test
    public void m3(){

    }

}
